The invention is based on a priority application EP06300773.6 which is hereby incorporated by reference.
The invention relates to a method, a computer software product, a telecommunication device and a telecommunication system for retrieving content of a distributed directory.
Communication systems with low operating expenditures (OPEX) having a minimum centralized infrastructure often use highly distributed databases in overlay networks (e.g. peer-to-peer networks). They implement self-organizing mechanisms to create a robust topology and to ensure consistency of the stored data. The use of load balancing, backup strategies and intelligent routing of database queries increases and service invocations have an impact on the overall efficiency of those networks.
I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan, described in “CHORD: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”. IEEE/ACM Transactions on Networking, Vol 11, No 1 (February 2003), pp. 17-32, a solution that forms an overlay ring topology and creates redundant links to its succeeding network nodes. The redundant links enable the network to endure the failure of a node. Each node is part of a distributed database used for lookup issues and thus is responsible for a specific part of the complete stored data. Queries to the database are routed to successor nodes along the ring or along some shortcuts, called fingers, until it reaches the one who is responsible. For backup reasons in case of node failure each nodes forward its data to its successor node(s).
The Chord protocol specifies how to find a location of keys, how new nodes join the system, and how to recover from the failure (or planned departure) of existing nodes. At its heart, Chord provides fast distributed computation of a hash function mapping keys to nodes responsible for them. It uses consistent hashing. With high probability a hash function balances load, i.e. all nodes receive roughly the same number of keys. Also with high probability, when a node joins (or leaves) the network, only a limited fraction of the keys are moved to a different location.
Chord improves the scalability of consistent hashing by avoiding the requirement that every node knows about every other node. A Chord node needs only few routing information. Because this information is distributed, a node resolves the hash function by communicating with a few other nodes. A lookup messages requires O(log n) hops. Chord must update the routing information when a node joins or leaves the network; a join or leave requires O(log2 n) messages.
The consistent hash function assigns each node and key an identifier using a base hash function. A node's identifier is chosen by hashing the node's IP address, while a key identifier is produced by hashing the key. Consistent hashing assigns keys to nodes as follows: Identifiers are (linearly ordered) arranged in an identifier circle, i.e. with respect to some modulo arithmetic. A key is assigned to the first node whose identifier is equal to or follows the identifier. This node is called the successor node of a key. Consistent hashing is designed to let nodes enter and leave the network with minimal disruption. To maintain the consistent hashing mapping when a node joins the network, certain keys previously assigned to a successor now become assigned to the joined node. When a node leaves the network, all of its assigned keys are reassigned to a successor.
Chord uses links to successor nodes for backup and routing issues. Therefore, the backup data cannot be leveraged for load balancing, as a request approaches the responsible node from behind, but the backup data is stored ahead along the ring.
Newly joining nodes have to wait passively until they are integrated into the network by their predecessor. This results in the effect that the joining time is not deterministic and statistically distributed. In advance routing database requests can be improved.